#include <iostream>
#include <vector>

void backtrack(const std::vector<int>& nums,
               int idx,
               int target,
               std::vector<int>& path,
               std::vector<std::vector<int>>& solutions) {
    if (target == 0) {
        solutions.push_back(path);
        return;
    }
    if (idx >= static_cast<int>(nums.size()) || target < 0) {
        return;
    }

    // 选择 nums[idx]
    path.push_back(nums[idx]);
    backtrack(nums, idx + 1, target - nums[idx], path, solutions);
    path.pop_back();

    // 跳过 nums[idx]
    backtrack(nums, idx + 1, target, path, solutions);
}

int main() {
    std::vector<int> nums = {2, 3, 5, 7};
    int target = 10;
    std::vector<int> path;
    std::vector<std::vector<int>> solutions;

    backtrack(nums, 0, target, path, solutions);

    std::cout << "Solutions (" << solutions.size() << "):\n";
    for (const auto& sol : solutions) {
        std::cout << "  {";
        for (size_t i = 0; i < sol.size(); ++i) {
            std::cout << sol[i];
            if (i + 1 < sol.size()) std::cout << ", ";
        }
        std::cout << "}\n";
    }
}
